package com.mgq.algorithm.array;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author MaGuangQi
 * @date 2021-12-28 13:55
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {6, 4, 7, 2, 5};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //生成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            //每次先把大根放到后面,然后heapSize-1,最后就变成从后面到前面有序了
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }

    }

    /**
     * 往堆中指定位置插入元素. 变成大根堆
     *
     * @param array
     * @param index
     */
    public static void heapInsert(int[] array, int index) {
        //孩子节点的值大于父节点
        while (array[index] > array[(index - 1) / 2]) {
            swap(array, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 从index位置重新堆化
     * index可能是整个堆的某个子树的根
     *
     * @param array
     * @param index
     * @param heapSize
     */
    private static void heapify(int[] array, int index, int heapSize) {
        //获取左孩子下标
        int left = index * 2 + 1;
        while (left < heapSize) {
            //找出左孩子和右孩子的最大下标
            int largest = left + 1 < heapSize && array[left + 1] > array[left] ? left+1 : left ;
            //和根比较
            largest = array[largest] > array[index] ? largest : index;
            if (largest == index) {
                //根最大
                break;
            }
            swap(array, largest, index);
            //index 往下走.
            index = largest;
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;

    }
}
